(Problem) 006 Sum square difference

작성일 In 댓글:

Project Euler

  • 공식 홈페이지 - projecteuler.net
  • 한글 번역 - projecteuler @kr
  • (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Sum square difference


problem <번역>

solution

Simple Code

컴퓨터는 연산이 빠르기 때문에 Brute Force한 방법으로 그냥 단순히 반복문을 통해 다 더하여 답을 구할 수도 있다.

006_sum_square_difference.py
def sum_of_num(n):
  total = 0
  for i in range(1, n+1):
      total += i

  return total**2


def sum_of_square_num(n):
  total = 0
  for i in range(1, n+1):
      total += i**2

  return total


print(sum_of_num(100) - sum_of_square_num(100))
HackerRank

하지만 조금이라도 효율적인 성능을 이끌어 내기 위해서는 수식을 이용한 풀이가 더 적당할 것 같다.
n까지의 단순 합은 n(n+1)/2와 같고
n까지의 제곱 합은 (2n+1)(n+1)n/6과 같다.

006_for_HacerRank.py
def sum_of_num(n):
  total = n*(n + 1)//2
  return total**2


def sum_of_square_num(n):
  return (2*n + 1)*(n + 1)*n//6


if __name__ == '__main__':
  for _ in range(int(input())):
      num = int(input())
      print(sum_of_num(num) - sum_of_square_num(num))

제곱의 합 공식